POST GRADUATE GOVERNMENT COLLEGE FOR GIRLS
SECTOR 11, CHANDIGARH
PRACTICAL FILE OF DATA STRUCTURE
SUBMITTED BY:
ARITIKA SHARMA
CLASS: BCA-II
ROLL NO.: 11001/22
SUBMITTED TO:
NAVDEEP KAUR MA’AM
(ASSISTANT PROFESSOR
DEPARTMENT OF COMPUTER
APPLICATIONS)
INDEX
Sr No.
Topic
Page No.
1
Copy An Element Into An Array
1-2
2
Entering Data Into Two-Dimensional
Array From User
3-4
3
Traversal Of Array
5-6
4
Program To Create A Link List
7-9
5
Program To Create A Double Link List
10-15
6
Program To Create A Stack Using
Pointer
16-18
7
Program To Create Sum Of Stack
19-21
8
Dynamic Stack Along With Its Two
Operations, Push & Pop
22-24
9
Program To Evaluate Postfix Notation
25-27
10
Program To Convert Infix Notation To
Postfix Notation
28-30
11
Program For Parenthesis Matching
Using Stack
31-33
12
Program To Create A Linear Queue
34-36
13
Program To Create Circular Queue
37-40
14
Program To Create Queue Using Linked
List
41-44
15
Program To Implement Binary Tree
45-51
16
Program To Create Linear Search
52-53
17
Program To Create Binary Search
54-55
18
Program To Sort ‘N’ Elements Using
Selection Sort
56-57
19
Program To Sort ‘N’ Elements Using
Bubble Sort
58-59
20
Program To Sort ‘N’ Elements Using
Insertion Sort
60-61
21
Program To Sort ‘N’ Elements Using
Quick Sort
62-64
22
Program On Breadth First Search
Method Of Traversing A Graph
Represented Using Adjacency Matrix
65-67
1
COPY AN ELEMENT INTO AN ARRAY
#include <stdio.h>
#include <conio.h>
#define N 10
int main() {
int la[N], lb[N];
int i;
printf("Enter %d elements of an Array\n", N);
for (i = 0; i < N; i++) {
scanf("%d", &la[i]);
}
for (i = 0; i < N; i++) {
lb[i] = la[i];
}
printf("\n Copied Elements of Array are:\n");
for (i = 0; i < N; i++) {
printf("%d\n", lb[i]);
}
getch();
return 0;
}
2
3
ENTERING DATA INTO TWO-DIMENSIONAL ARRAY FROM
USER
#include<stdio.h>
#include<conio.h>
int main(){
int a[3][4];
int i,j;
for(i=0;i<3;i++){
for(j=0;j<4;j++){
printf("Enter number ");
scanf("%d",&a[i][j]);
}
}
printf("Data entered is =\n");
for(i=0;i<3;i++){
for(j=0;j<4;j++){
printf("%d\t",a[i][j]);
}
printf("\n");
}
getch();
}
4
5
TRAVERSAL OF ARRAY
#include<stdio.h>
#include<conio.h>
#define N 10
int main(){
int la[N];
int i;
printf("\n Enter %d element of an Array \n",N);
for(i=0;i<N;i++){
scanf("%d",&la[i]);
}
printf("\nElement of Array are ");
for(i=0;i<N;i++){
printf("\n%d",la[i]);
}
getch();
}
6
7
PROGRAM TO CREATE A LINK LIST
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node{
int data;
struct node *next;
};
struct node* beggin(struct node *head,int data){
struct node* ptr=(struct node*)malloc(sizeof(struct node));
ptr->next=head;
ptr->data=data;
return ptr;
}
struct node* between(struct node *head,int data,int index){
struct node* ptr=(struct node*) malloc(sizeof(struct node));
struct node *p=head;
int i=0;
while(i!=index-1){
p=p->next;
i++;
}
ptr->data=data;
ptr->next=p->next;
p->next=ptr;
return head;
}
struct node* end(struct node *head,int data){
struct node* ptr=(struct node*)malloc(sizeof(struct node));
struct node *p=head;
while(p->next!=NULL){
p=p->next;
}
ptr->data=data;
p->next=ptr;
ptr->next=NULL;
return head;
}
struct node* afternode(struct node *head, struct node *pre,int data){
struct node* ptr=(struct node*) malloc(sizeof(struct node));
ptr->data=data;
ptr->next=pre->next;
pre->next=ptr;
return head;
8
}
void triverse(struct node *ptr){
while(ptr!=NULL){
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
void main(){
struct node *head;
struct node *second;
struct node *third;
head=(struct node*) malloc(sizeof(struct node));
second=(struct node*) malloc(sizeof(struct node));
third=(struct node*) malloc(sizeof(struct node));
head->data=7;
head->next=second;
second->data=10;
second->next=third;
third->data=11;
third->next=NULL;
triverse(head);
head=beggin(head,14);
printf("\n");
triverse(head);
printf("\n");
head=between(head,77,2);
triverse(head);
printf("\n");
head=end(head,1);
triverse(head);
printf("\n");
head=afternode(head,second,13);
triverse(head);
getch();
}
9
10
PROGRAM TO CREATE A DOUBLE LINK LIST
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
struct Node* head = NULL;
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning of the list
void insertAtBeginning(int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
// Function to insert a node at the end of the list
void insertAtEnd(int data) {
struct Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
} else {
struct Node* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
11
}
}
// Function to insert a node at a specific position in the list
void insertAtPosition(int data, int position) {
if (position < 1) {
printf("Invalid position\n");
return;
}
struct Node* newNode = createNode(data);
if (position == 1) {
newNode->next = head;
head->prev = newNode;
head = newNode;
} else {
struct Node* current = head;
int i = 1;
while (i < position - 1 && current != NULL) {
current = current->next;
i++;
}
if (current == NULL) {
printf("Invalid position\n");
return;
}
newNode->next = current->next;
if (current->next != NULL) {
current->next->prev = newNode;
}
current->next = newNode;
newNode->prev = current;
}
}
// Function to delete a node by value
void deleteNode(int data) {
struct Node* current = head;
while (current != NULL) {
if (current->data == data) {
if (current->prev != NULL) {
current->prev->next = current->next;
} else {
head = current->next;
}
if (current->next != NULL) {
current->next->prev = current->prev;
12
}
free(current);
printf("Node with data %d deleted\n", data);
return;
}
current = current->next;
}
printf("Node with data %d not found\n", data);
}
// Function to search for a node by value
void searchNode(int data) {
struct Node* current = head;
int position = 1;
while (current != NULL) {
if (current->data == data) {
printf("Node with data %d found at position %d\n", data, position);
return;
}
current = current->next;
position++;
}
printf("Node with data %d not found\n", data);
}
// Function to display the list in the forward direction
void displayForward() {
struct Node* current = head;
printf("List in forward direction: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
// Function to display the list in the backward direction
void displayBackward() {
struct Node* current = head;
if (current == NULL) {
printf("List is empty\n");
return;
}
while (current->next != NULL) {
current = current->next;
}
13
printf("List in backward direction: NULL");
while (current != NULL) {
printf(" <- %d", current->data);
current = current->prev;
}
printf("\n");
}
int main() {
int choice, data, position;
while (1) {
printf("\nDoubly Linked List Operations:\n");
printf("1. Insert at the beginning\n");
printf("2. Insert at the end\n");
printf("3. Insert at a specific position\n");
printf("4. Delete a node\n");
printf("5. Search for a node\n");
printf("6. Display the list in forward direction\n");
printf("7. Display the list in backward direction\n");
printf("8. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter data to insert at the beginning: ");
scanf("%d", &data);
insertAtBeginning(data);
break;
case 2:
printf("Enter data to insert at the end: ");
scanf("%d", &data);
insertAtEnd(data);
break;
case 3:
printf("Enter data to insert: ");
scanf("%d", &data);
printf("Enter position to insert: ");
scanf("%d", &position);
insertAtPosition(data, position);
break;
case 4:
printf("Enter data to delete: ");
scanf("%d", &data);
deleteNode(data);
14
break;
case 5:
printf("Enter data to search: ");
scanf("%d", &data);
searchNode(data);
break;
case 6:
displayForward();
break;
case 7:
displayBackward();
break;
case 8:
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0;
}
15
16
PROGRAM TO CREATE A STACK USING POINTER
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#define max 3
int i;
typedef struct stack
{
int *N;
int top;
}stack;
void push(stack *s)
{
if(s->top==(max-1))
{
printf("STACK OVERFLOW");
return;
}
printf("ENTER AN ELEMENT\t");
scanf("%d",&s->N[++s->top]);
}
void pop(stack *s)
{
if(s->top==-1)
{
printf("STACK UNDERFLOW");
return;
}
printf("POPED ELEMENT IS %d",s->N[s->top--]);
}
void show(stack *s)
{
for(i=0;i <= s->top;i++)
printf("%d\t",s->N[i]);
}
int main()
{
stack s1;
s1.top=-1;
s1.N=(int*)malloc(sizeof(int)*max);
17
while(1)
{
printf("ENTER YOUR CHOICE :\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Show\n");
printf("4. Exit\n");
scanf("%d",&i);
switch(i)
{
case 1:
push(&s1);
break;
case 2:
pop(&s1);
break;
case 3:
show(&s1);
break;
case 4:
exit(0);
}
getch();
}
}
18
19
PROGRAM TO CREATE SUM OF STACK
#include<stdio.h>
#include<conio.h>
#define max 10
int ch;
struct stack{
int arr[max];
int curpos;
}s1;
void push(){
if(s1.curpos==(max-1)){
printf("stack overflow");
return;
}
printf("enter the element");
scanf("%d",&s1.arr[++s1.curpos]);}
void pop(){
if (s1.curpos==-1){
printf("underflow");
return;
}
printf("pop element is %d",s1.arr[s1.curpos--]);
}
void show(){
for(ch=0;ch<=s1.curpos;ch++){
printf("%d\n",s1.arr[ch]);
}
}
void sum(){
int s;
for(ch=0;ch<=s1.curpos;ch++){
s+=s1.arr[ch];}
printf("sum of stack is %d ",s);}
void assend(){
for(ch=0;ch<=s1.curpos;ch++){
if((s1.arr[0]>s1.arr[1])&&(s1.arr[0]>s1.arr[2])){
printf("%d",s1.arr[0]);
}else if((s1.arr[1]>s1.arr[0])&&(s1.arr[1]>s1.arr[2])){
printf("%d",s1.arr[1]);
}else{printf("%d",s1.arr[2]);
20
}
}}
void minmax(){
int max_sum;
int min_sum;
int current_sum = 0;
for (ch=0;ch<=s1.curpos;ch++) {
current_sum += s1.arr[ch];
if (current_sum > max_sum) {
max_sum = current_sum;
}
if (current_sum < 0) {
current_sum = 0;
}
if (current_sum < min_sum) {
min_sum = current_sum;
}
}
printf("Maximum sum: %d\n", max_sum);
printf("Minimum sum: %d\n", min_sum);
}
void main(){
s1.curpos=-1;
while(1){
printf("\n1 push\n");
printf("2 pop\n");
printf("3. show \n");
printf("4 exit\n");
printf("5 sum\n");
printf("6 minmax\n");
scanf("%d",&ch);
switch(ch){
case 1 : push();break;
case 2: pop();break;
case 3 : show(); break;
case 4: exit(0);break;
case 5: sum();break;
case 6: minmax();}
}
getch();}
21
22
DYNAMIC STACK ALONG WITH ITS TWO OPERATIONS, PUSH
& POP
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a stack node
struct Node {
int data;
struct Node* next;
};
// Function to create a new stack node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
if (!node) {
printf("Memory allocation failed.\n");
exit(1);
}
node->data = data;
node->next = NULL;
return node;
}
// Function to check if the stack is empty
int isEmpty(struct Node* root) {
return (root == NULL);
}
// Function to push an element onto the stack
void push(struct Node** root, int data) {
struct Node* node = newNode(data);
node->next = *root;
*root = node;
printf("%d pushed to the stack.\n", data);
}
// Function to pop an element from the stack
int pop(struct Node** root) {
if (isEmpty(*root)) {
printf("Stack is empty.\n");
exit(1);
}
struct Node* temp = *root;
*root = (*root)->next;
23
int popped = temp->data;
free(temp);
return popped;
}
// Function to display the elements in the stack
void displayStack(struct Node* root) {
while (root != NULL) {
printf("%d ", root->data);
root = root->next;
}
printf("\n");
}
int main() {
struct Node* root = NULL;
push(&root, 10);
push(&root, 20);
push(&root, 30);
printf("Stack elements: ");
displayStack(root);
printf("%d popped from the stack.\n", pop(&root));
printf("Stack elements after pop: ");
displayStack(root);
return 0;
}
24
25
PROGRAM TO EVALUATE POSTFIX NOTATION
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#define N 40
int stack[N];
int top=-1;
void push(int n){
if(top==N-1){
printf("Stack is full\n");
return;
}
else{
top=top+1;
stack[top]=n;
printf("Pushed element is %d\n",n);
}
}
int pop(){
int n;
if(top==-1){
printf("Stack is empty\n");
return;
}
else{
n=stack[top];
top=top-1;
printf("The poped element is %d\n",n);
return(n);
}
}
int evaluate(int op1, int op2,char ch){
int n;
printf("op1=%d op2=%d ch=%c\n",op1,op2,ch);
if(op1<op2){
n=op1;
op1=op2;
op2=n;
}
if(ch=='+')
n=op1+op2;
else if(ch=='-')
n= op2-op1;
else if(ch=='*')
n=op1*op2;
26
else if(ch=='/')
n =op1/op2;
else if(ch=='%')
n = op1%op2;
else{
printf("The operator is not identified\n");
exit(0);
}
printf("n=%d\n",n);
return(n);
}
int main(){
char str[50],ch,ch1;
int i=0,n,op1,op2;
printf("Enter the Postfix string \n");
scanf("%s",str);
ch=str[i];
while(ch!='\0'){printf("The char is = %c\n",ch);
if(isdigit(ch)){
n=ch-'0';
push(n);
}
else{
op1=pop();
op2=pop();
n=evaluate(op1,op2,ch);
push(n);
}
ch=str[++i];
}
printf("The value of the arithmetic expression is =%d\n",pop());
return 0;
}
27
28
PROGRAM TO CONVERT INFIX NOTATION TO POSTFIX
NOTATION
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_EXPRESSION_LENGTH 100
// Function to check if a character is an operator
int isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^');
}
// Function to get the precedence of an operator
int getPrecedence(char op) {
if (op == '^') return 3;
else if (op == '*' || op == '/') return 2;
else if (op == '+' || op == '-') return 1;
return 0; // Lowest precedence
}
// Function to convert infix expression to postfix expression
void infixToPostfix(char infix[], char postfix[]) {
int i, j;
char stack[MAX_EXPRESSION_LENGTH];
int top = -1;
for (i = 0, j = 0; i < strlen(infix); i++) {
char ch = infix[i];
if (isalnum(ch)) {
postfix[j++] = ch;
} else if (ch == '(') {
stack[++top] = ch;
} else if (ch == ')') {
while (top >= 0 && stack[top] != '(') {
postfix[j++] = stack[top--];
}
if (top >= 0 && stack[top] == '(') {
top--; // Pop '(' from the stack
}
} else if (isOperator(ch)) {
while (top >= 0 && getPrecedence(ch) <= getPrecedence(stack[top])) {
postfix[j++] = stack[top--];
}
29
stack[++top] = ch;
}
}
while (top >= 0) {
postfix[j++] = stack[top--];
}
postfix[j] = '\0';
}
int main() {
char infix[MAX_EXPRESSION_LENGTH];
char postfix[MAX_EXPRESSION_LENGTH];
printf("Enter an infix expression: ");
scanf("%s", infix);
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
return 0;
}
30
31
PROGRAM FOR PARENTHESIS MATCHING USING STACK
#include <stdio.h>
#include <stdbool.h>
#define MAXSIZE 50
struct stack {
int top;
char items[MAXSIZE]; // Changed to store characters
};
void push(struct stack*, char);
char pop(struct stack*);
bool isEmpty(struct stack*);
int main() {
char expression[MAXSIZE];
int i = -1;
struct stack mystack;
mystack.top = -1;
printf("\n Enter the expression ->");
scanf("%s", expression);
while (expression[++i] != '\0') {
switch (expression[i]) {
case '(':
case '[':
case '{':
push(&mystack, expression[i]);
break;
case ')':
if (pop(&mystack) != '(') {
printf("\n Expression has unmatched parentheses");
return 0;
}
break;
case ']':
if (pop(&mystack) != '[') {
printf("\n Expression has unmatched square brackets");
return 0;
}
break;
case '}':
if (pop(&mystack) != '{') {
32
printf("\n Expression has unmatched curly braces");
return 0;
}
break;
}
}
if (isEmpty(&mystack)) {
printf("\n Expression is okay");
} else {
printf("\n Expression has unmatched parentheses");
}
return 0;
}
void push(struct stack *mystack, char item) {
if (mystack->top == MAXSIZE - 1) {
printf("\n Stack Overflow\n");
} else {
mystack->items[++mystack->top] = item;
}
}
char pop(struct stack *mystack) {
if (isEmpty(mystack)) {
printf("\n Stack Underflow\n");
return '\0'; // Return a null character to indicate an error
}
return mystack->items[mystack->top--];
}
bool isEmpty(struct stack *mystack) {
return (mystack->top == -1);
}
33
34
PROGRAM TO CREATE A LINEAR QUEUE
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
struct Queue {
int items[MAX_SIZE];
int front;
int rear;
};
// Function to initialize the queue
void initializeQueue(struct Queue *q) {
q->front = -1;
q->rear = -1;
}
// Function to check if the queue is empty
int isEmpty(struct Queue *q) {
return (q->front == -1);
}
// Function to check if the queue is full
int isFull(struct Queue *q) {
return (q->rear == MAX_SIZE - 1);
}
// Function to enqueue (insert) an element
void enqueue(struct Queue *q, int value) {
if (isFull(q)) {
printf("Queue is full. Cannot enqueue.\n");
} else {
if (isEmpty(q)) {
q->front = 0;
}
q->rear++;
q->items[q->rear] = value;
printf("Enqueued: %d\n", value);
}
}
// Function to dequeue (remove) an element
int dequeue(struct Queue *q) {
int item;
35
if (isEmpty(q)) {
printf("Queue is empty. Cannot dequeue.\n");
return -1;
} else {
item = q->items[q->front];
if (q->front == q->rear) {
q->front = -1;
q->rear = -1;
} else {
q->front++;
}
return item;
}
}
int main() {
struct Queue queue;
initializeQueue(&queue);
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
int dequeued = dequeue(&queue);
if (dequeued != -1) {
printf("Dequeued: %d\n", dequeued);
}
enqueue(&queue, 40);
return 0;
}
36
37
PROGRAM TO CREATE CIRCULAR QUEUE
#include <stdio.h>
#include <conio.h>
#include <process.h>
#define N 5
int q[N], front = -1, rear = -1, item;
void qinsert(int item) {
if ((front == 0 && rear == N - 1) || (front == rear + 1)) {
printf("\n Queue is Full ");
getch();
return;
}
if (front == -1)
front = rear = 0;
else if (rear == N - 1)
rear = 0;
else
rear = rear + 1;
q[rear] = item;
}
int qdelete(void) {
if (front == -1) {
printf("\n Queue is Empty");
getch();
return -1;
}
item = q[front];
if (front == rear)
front = rear = -1;
else if (front == N - 1)
front = 0;
else
front = front + 1;
return item;
}
void qdisplay(void) {
if (front == -1) {
printf("\n Queue is Empty");
} else {
int i = front;
printf("\n Queue Contents: ");
38
while (1) {
printf("%d ", q[i]);
if (i == rear) {
break;
}
if (i == N - 1) {
i = 0;
} else {
i++;
}
}
}
getch();
}
int main() {
int ch;
front = rear = -1;
while (1) {
printf("\n***********MAIN MENU************");
printf("\n 1. Insert");
printf("\n 2. Delete");
printf("\n 3. Display Queue");
printf("\n 4. Exit");
printf("\n Enter your choice: ");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("\n Enter the element: ");
scanf("%d", &item);
qinsert(item);
break;
case 2:
item = qdelete();
if (item != -1) {
printf("\n Item = %d ", item);
}
break;
case 3:
qdisplay();
break;
case 4:
exit(1);
break;
default:
printf("\n Invalid choice ");
39
}
}
}
40
41
PROGRAM TO CREATE QUEUE USING LINKED LIST
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node* front;
struct Node* rear;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to initialize an empty queue
void initializeQueue(struct Queue* queue) {
queue->front = NULL;
queue->rear = NULL;
}
// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
return queue->front == NULL;
}
// Function to enqueue (insert) an element
void enqueue(struct Queue* queue, int data) {
struct Node* newNode = createNode(data);
if (isEmpty(queue)) {
queue->front = newNode;
queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
}
42
// Function to dequeue (remove) an element
int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty. Dequeue operation not possible.\n");
return -1; // Return a sentinel value for an empty queue
}
int data = queue->front->data;
struct Node* temp = queue->front;
queue->front = queue->front->next;
free(temp);
if (queue->front == NULL) {
queue->rear = NULL;
}
return data;
}
// Function to display the elements in the queue
void display(struct Queue* queue) {
struct Node* current = queue->front;
printf("Queue elements: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
struct Queue queue;
initializeQueue(&queue);
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
display(&queue);
int dequeued = dequeue(&queue);
if (dequeued != -1) {
printf("Dequeued: %d\n", dequeued);
}
43
display(&queue);
return 0;
}
44
45
PROGRAM TO IMPLEMENT BINARY TREE
#include <stdio.h>
#include <stdlib.h>
struct node {
int info;
struct node *left, *right;
};
struct node *Root = NULL;
struct node *find(int item) {
struct node *loc = NULL, *ptr = Root, *save = NULL;
while (ptr != NULL) {
save = ptr;
if (item == ptr->info) {
loc = ptr;
break;
} else if (item < ptr->info) {
ptr = ptr->left;
} else {
ptr = ptr->right;
}
}
return loc;
}
void insert(int item) {
struct node *new1, *loc, *par;
loc = find(item);
if (loc != NULL) {
printf("\n Duplicate Item can not be inserted");
return;
}
new1 = (struct node *)malloc(sizeof(struct node));
if (new1 == NULL) {
printf("\n Overflow");
return;
}
new1->info = item;
new1->left = NULL;
new1->right = NULL;
if (Root == NULL) {
Root = new1;
46
} else {
loc = Root;
while (loc != NULL) {
par = loc;
if (item < loc->info) {
loc = loc->left;
} else {
loc = loc->right;
}
}
if (item < par->info) {
par->left = new1;
} else {
par->right = new1;
}
}
}
void inorder(struct node *R) {
if (R != NULL) {
inorder(R->left);
printf(" %d ", R->info);
inorder(R->right);
}
}
void preorder(struct node *R) {
if (R != NULL) {
printf(" %d ", R->info);
preorder(R->left);
preorder(R->right);
}
}
void postorder(struct node *R) {
if (R != NULL) {
postorder(R->left);
postorder(R->right);
printf(" %d ", R->info);
}
}
struct node *search(int item) {
struct node *ptr = Root;
while (ptr != NULL) {
if (item == ptr->info) {
47
return ptr;
} else if (item < ptr->info) {
ptr = ptr->left;
} else {
ptr = ptr->right;
}
}
return NULL;
}
void del(int item) {
struct node *ptr = Root, *back = NULL, *successor = NULL;
if (Root == NULL) {
printf("Tree is empty");
return;
}
while (ptr != NULL) {
if (item == ptr->info) {
break;
}
back = ptr;
if (item < ptr->info) {
ptr = ptr->left;
} else {
ptr = ptr->right;
}
}
if (ptr == NULL) {
printf("Item not found");
return;
}
if (ptr->left != NULL && ptr->right != NULL) {
back = ptr;
successor = ptr->right;
while (successor->left != NULL) {
back = successor;
successor = successor->left;
}
ptr->info = successor->info;
ptr = successor;
}
if (ptr->left == NULL && ptr->right == NULL) {
if (ptr == Root) {
Root = NULL;
48
} else if (back->left == ptr) {
back->left = NULL;
} else {
back->right = NULL;
}
free(ptr);
} else if (ptr->left == NULL && ptr->right != NULL) {
if (ptr == Root) {
Root = ptr->right;
} else if (back->left == ptr) {
back->left = ptr->right;
} else {
back->right = ptr->right;
}
free(ptr);
}
}
int main() {
int item, ch;
while (1) {
printf("\n***********MAIN MENU************");
printf("\n 1. Insert");
printf("\n 2. Inorder");
printf("\n 3. Preorder");
printf("\n 4. Postorder");
printf("\n 5. Delete");
printf("\n 6. Search");
printf("\n 7. Exit");
printf("\n Enter your choice: ");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("\n Enter item to Insert: ");
scanf("%d", &item);
insert(item);
break;
case 2:
printf("Inorder Traversal: ");
inorder(Root);
printf("\n");
break;
case 3:
printf("Preorder Traversal: ");
preorder(Root);
printf("\n");
49
break;
case 4:
printf("Postorder Traversal: ");
postorder(Root);
printf("\n");
break;
case 5:
printf("Enter the element to delete: ");
scanf("%d", &item);
del(item);
break;
case 6:
printf("Enter the element to search: ");
scanf("%d", &item);
struct node *result = search(item);
if (result != NULL) {
printf("Item found: %d\n", result->info);
} else {
printf("Item not found\n");
}
break;
case 7:
exit(0);
default:
printf("\n Invalid choice ");
}
}
}
50
51
52
PROGRAM TO CREATE LINEAR SEARCH
#include<stdio.h>
#include<conio.h>
#define N 10
int main()
{
int arr[N],loc,item;
int i;
printf("\n Enter %d elements of an Array :",N);
for(i=0;i<N;i++)
{
scanf("%d",&arr[i]);
}
printf("\nEnter item to be search :");
scanf("%d",&item);
loc=NULL;
for(i=0;i<N;i++)
{
if(item==arr[i])
{
loc=i+1;
break;
}
}
if(loc==NULL)
{
printf("\nItem %d not found in list",item);
}
else
{
printf("\nItem %d found at %d location",item,loc);
}
getch();
}
53
54
PROGRAM TO CREATE BINARY SEARCH
#include<stdio.h>
#define N 6
void main(){
int a[N],item,beg,end,mid;
int i;
printf("\n Enter %d element of an Array\n",N);
for(i=0;i<N;i++){
scanf("%d",&a[i]);
}
printf("\n Enter item to be search");
scanf("%d",&item);
beg = 0;
end=N-1;
mid=(beg+end)/2;
while(beg<=end && a[mid]!=item){
if(a[mid]>item)
end=mid-1;
else
beg=mid+1;
mid=(beg+end)/2;
}
if(a[mid]!=item){
printf("\n Item %d Not found in List",item);
}
else
{
printf("\n Item %d found at %d location ", item,mid+1);
}
}
55
56
PROGRAM TO SORT ‘N’ ELEMENTS USING SELECTION SORT
#include<stdio.h>
#include<conio.h>
#define N 10
void main(){
int a[N],i,j,t,min,loc;
printf("\n Enter the elements");
for(i=0;i<N;i++)
scanf("%d",&a[i]);
for(i=0;i<N-1;i++){
min=a[i];
loc=i;
for(j=i+1;j<N;j++){
if(min>a[j])
{
min=a[j];
loc=j;
}
}
t=a[i];
a[i] = a[loc];
a[loc]=t;
}
printf("\n Sorted elements of array \n");
for(i=0;i<N;i++){
printf("\t %d",a[i]);
}
printf("\n");
return 0;
}
57
58
PROGRAM TO SORT ‘N; ELEMENTS USING BUBBLE SORT
#include<stdio.h>
#include<conio.h>
#define N 5
int main()
{
int a[N],p,c,t;
int i;
printf("\nEnter %d elements of an Array :",N);
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
}
for(p=1;p<=N-1;p++)
{
for(c=0;c<N-p;c++)
{
if(a[c]>a[c+1])
{
t=a[c];
a[c]=a[c+1];
a[c+1]=t;
}
}
}
printf("\nSorted Array :");
for(i=0;i<=N-1;i++)
{
printf("\t%d",a[i]);
}
getch();
}
59
60
PROGRAM TO SORT ‘N’ ELEMENTS USING INSERTION SORT
#include<stdio.h>
#include<conio.h>
#define N 10
int main(){
int a[N],i,k,temp,ptr;
printf("Enter the elements");
for(i=0;i<N;i++)
scanf("%d",&a[i]);
for(k=1;k<N;k++){
temp=a[k];
ptr=k-1;
while(temp<a[ptr] && ptr>=0){
a[ptr+1]=a[ptr];
ptr--;
}
a[ptr+1]=temp;
}
printf("\n Sorted Array ");
for(i=0;i<N;i++){
printf("\t %d",a[i]);
}
return 0;
}
61
62
PREOGRAM TO SORT ‘N’ ELEMENTS USING QUICK SORT
#include <stdio.h>
#include <conio.h>
#define N 20
void q_sort(int *, int, int);
void q_sort(int array[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = array[left];
while (left < right)
{
while ((array[right] >= pivot)&&(left<right))
right--;
if (left != right)
{
array[left] = array[right];
left++;
}
while ((array[left] <= pivot) && (left < right))
left++;
if (left != right)
{
array[right] = array[left];
right--;
}
}
array[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
{
q_sort(array, left, pivot - 1);
}
if (right > pivot)
{
q_sort(array, pivot + 1, right);
}
}
int main()
{
63
int a[N], i, size;
//clrscr();
printf("\nEnter the size of list :");
scanf("%d", &size);
printf("Enter %d elements of the list to be sort :", size);
for (i = 0; i < size; i++)
{
scanf("%d", &a[i]);
}
q_sort(a, 0, size - 1);
printf("Elements after sorting are :");
for (i = 0; i < size; i++)
{
printf("%d\t", a[i]);
}
}
64
65
PROGRAM ON BREADTH FIRST SEARCH METHOD OF
TRAVERSING A GRAPH REPRESENTED USING ADJACENCY
MATRIX
#include<stdio.h>
#include<conio.h>
#define MAX 20
typedef struct queue {
int r, f;
int item[MAX];
}que;
int full(que *p);
int empty(que *p);
void insert(que *p,int x);
int delete(que *p);
void bfs(int v);
int a[MAX][MAX];
int n;
int main(){
int i, j,v;
printf("\n Enter number of vertices : ");
scanf("%d",&n);
printf("\n Enter adjacency matrix of graph : ");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf("\n Enter the starting node for BFS : ");
scanf("%d",&v);
bfs(v);
getch();
}
void bfs(int v){
int visit[20], i;
que q;
q.r=q.f=-1;
for(i=0;i<n;i++)
visit[i]=0;
insert(&q,v);
printf("\n Visit %d",v);
visit[v] = 1;
while(! empty(&q)){
v=delete(&q);
for(i=0;i<n;i++){
if((visit[i]==0)&&(a[v][i]!=0)){\
66
insert(&q,i);
visit[i]=1;
printf("\n visit %d",i);
}
}
}
}
int empty(que *p){
if(p->r==-1)
return(1);
return(0);
}
int full(que *p){
if(p->r==MAX-1)
return(1);
return(0);
}
void insert(que *p,int x){
if(p->r==-1){
p->r=p->f=0;
p->item[p->r]=x;
}
else
{
p->r=p->r+1;
p->item[p->r]=x;
}
}
int delete(que *p){
int x;
x= p->item[p->f];
if(p->r==p->f){
p->r=-1;
p->f=-1;
}
else
p->f=p->f+1;
return(x);
}
67